package com.lcm.algorithm.datatest.sort;

/**
 * @description:
 * @author: lcm
 * @create: 2020-04-03 10:31
 **/

public class QuickSort {

        public static void main(String[] args) {
            int n[] = { 6, 5, 2, 7, 3, 9, 8, 4, 10, 1 };
            quicksort(n);
            System.out.print("快排结果：");
            for (int m : n) {
                System.out.print(m + " ");
            }
        }

        public static void quicksort(int n[]) {
            quicksort(n, 0, n.length - 1);
        }

        public static void quicksort(int n[], int l, int r) {
            if (l < r) {
                // 一趟快排，并返回交换后基数的下标
                int index = patition(n, l, r);
                // 递归排序基数左边的数组
                quicksort(n, l, index - 1);
                // 递归排序基数右边的数组
                quicksort(n, index + 1, r);
            }

        }

        @SuppressWarnings("Duplicates")
        public static int patition(int nums[], int from, int to) {
            // 设数组的第一个数为标兵
            int p = nums[from];
            //左开始位置
            int left = from;
            //右开始位置
            int right = to;
            while (left < right) {
                // 找到右边第一个小于基数的数
                while (nums[right] >= p && left < right) {
                    right --;
                }
                // 找到左边第一个大于基数的数
                while (nums[left] <= p && left < right) {
                    left++;
                }
                // 交换两个数
                swap(nums, left, right);
            }
            //让标兵站中间
            swap(nums, from, left);
            return left;
        }

        private static void swap(int n[], int i, int j) {
            int temp = n[i];
            n[i] = n[j];
            n[j] = temp;
        }


}
